package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 递增的三元子序列
 * 334 increasing-triplet-subsequence
 * @author: Zhang Bo
 * @create: 2022-04-10 12:52:52
 **/
public class IncreasingTripletSubsequence {
    public static void main(String[] args) {
//        int[] nums = {1,2,3,4,5};
        int[] nums = {2,1,5,0,4,6};
        Solution solution = new IncreasingTripletSubsequence().new Solution();
        System.out.println(solution.increasingTriplet(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * min始终记录最小元素，med 为某个子序列里第二大的数。
         *
         * 接下来不断更新 min，同时保持 med 尽可能的小。
         *
         * 如果下一个元素比 med 大，说明找到了三元组。
         * @param nums
         * @return
         */
        public boolean increasingTriplet(int[] nums) {
            if (nums == null || nums.length < 3) {
                return false;
            }

            int min = Integer.MAX_VALUE;
            int med = Integer.MAX_VALUE;

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= min) {
                    min = nums[i];
                } else if (nums[i] <= med) {
                    med = nums[i];
                } else {
                    return true;
                }

            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
